package com.example.fib;

/**
 * 斐波那契数列
 * 求取斐波那契数列第N位的值
 * 斐波那契数列: 每一位的值等于他前两位数字之和，前两位固定是0和1。
 * 0，1，1，2，3，5，8，...
 */
public class Fib {

    /**
     * 暴力递归 O(2**n)
     * @param num 下标值
     * @return 数值
     */
    private static int calculate(int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        return calculate(num - 1) + calculate(num - 2);
    }

    /**
     * 去重递归
     * @param num 下标值
     * @return 数值
     */
    private static int calculateDistinct(int num) {
        int[] arr = new int[num + 1];
        return recurse(arr, num);
    }

    private static int recurse(int[] arr, int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        if (arr[num] != 0) {
            return arr[num];// 如果存在arr[num]就不继续递归
        }
        arr[num] = recurse(arr, num - 1) + recurse(arr, num - 2);
        return arr[num];
    }


    /**
     * 双指针迭代
     * @param num 下标值
     * @return 数组
     */
    private static int twoPoint(int num) {
        if (num == 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        int low = 0, high = 1;
        for (int i = 2; i <= num; i++) {
            int sum = low + high;
            low = high;
            high = sum;
        }
        return high;
    }

    public static void main(String[] args) {

        System.out.println(calculate(10));
        System.out.println(calculateDistinct(10));
        System.out.println(twoPoint(10));

    }

}
